//
// Created by hpf on 18-5-8.
//

#include <string>
#include <cassert>
#include <iostream>

class Solution {
public:
    bool isValid(std::string s) {
        ArrayStack<char> *stack = new ArrayStack<char>();
        for (int i = 0; i < s.size(); ++i) {
            char c = s.at(i);
            if (c == '(' || c == '[' || c == '{') {
                stack->push(c);
            } else {
                if (stack->isEmpty()) {
                    return false;
                }
                char topChar = stack->pop();
                if (c == ')' && topChar != '(') {
                    return false;
                }
                if (c == ']' && topChar != '[') {
                    return false;
                }
                if (c == '}' && topChar != '{') {
                    return false;
                }
            }
        }
        return stack->isEmpty();
    }

private:
    template<typename T>
    class Stack {
    public:
        virtual int getSize() = 0;

        virtual bool isEmpty() = 0;

        virtual void push(T e) = 0;

        virtual T pop() = 0;

        virtual T peek() = 0;
    };

    template<typename T>
    class Array {
    public:
        // 构造函数，传入数组的容量capacity构造Array
        Array(int capacity) {
            data = new T[capacity];
            size = 0;
            this->capacity = capacity;
        }

        // 无参数的构造函数，默认数组的容量capacity=10
        Array() {
            data = new T[5];
            size = 0;
            capacity = 5;
        }

        // 获取数组的容量
        int getCapacity() {
            return capacity;
        }

        // 获取数组中的元素个数
        int getSize() {
            return size;
        }

        // 返回数组是否为空
        bool isEmpty() {
            return size == 0;
        }

        // 在index索引的位置插入一个新元素e
        void add(int index, T e) {
            assert(index >= 0 && index <= size);
            if (size == capacity) {
                resize(2 * capacity);
            }
            for (int i = size - 1; i >= index; --i) {
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }

        // 在所有元素前添加一个新元素
        void addFirst(T e) {
            add(0, e);
        }

        // 向所有元素后添加一个新元素
        void addLast(T e) {
            add(size, e);
        }

        // 获取index索引位置的元素
        T get(int index) {
            assert(index >= 0 && index < size);
            return data[index];
        }

        // 获取索引位置为0的元素
        T getFirst() {
            return get(0);
        }

        // 获取最后索引位置的元素
        T getLast() {
            return get(size - 1);
        }

        // 修改index索引位置的元素为e
        void set(int index, T e) {
            assert(index >= 0 && index < size);
            data[index] = e;
        }

        // 查找数组中是否有元素e
        bool contains(T e) {
            for (int i = 0; i < size; ++i) {
                if (data[i] == e) {
                    return true;
                }
            }
            return false;
        }

        // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
        int find(T e) {
            for (int i = 0; i < size; ++i) {
                if (data[i] == e) {
                    return i;
                }
            }
            return -1;
        }

        // 从数组中删除index位置的元素, 返回删除的元素
        T remove(int index) {
            assert(index >= 0 && index < size);
            T ret = data[index];
            for (int i = index + 1; i < size; ++i) {
                data[i - 1] = data[i];
            }
            size--;
            if (size == capacity / 4 && capacity / 2 != 0) {
                resize(capacity / 2);
            }
            return ret;
        }

        // 从数组中删除第一个元素, 返回删除的元素
        T removeFirst() {
            return remove(0);
        }

        // 从数组中删除最后一个元素, 返回删除的元素
        T removeLast() {
            return remove(size - 1);
        }

        // 从数组中删除元素e
        void removeElement(T e) {
            int index = find(e);
            if (index != -1) {
                remove(index);
            }
        }

        //打印数组的所有元素
        void print() {
            std::cout << "[";
            for (int i = 0; i < size; ++i) {
                std::cout << data[i];
                if (i != size - 1) {
                    std::cout << ",";
                }
            }
            std::cout << "]";
        }
    

    private:
        T *data;
        int size;
        int capacity;

        // 将数组空间的容量变成newCapacity大小
        void resize(int newCapacity) {
            T *newData = new T[newCapacity];
            for (int i = 0; i < size; ++i) {
                newData[i] = data[i];
            }
            data = newData;
            capacity = newCapacity;
            newData = nullptr;
            delete []newData;
        }
    };

    template<typename T>
    class ArrayStack : public Stack<T> {
    public:
        ArrayStack(int capacity) {
            array = new Array<T>(capacity);
        }

        ArrayStack() {
            array = new Array<T>();
        }

        ~ArrayStack() {
            delete[] array;
            array = nullptr;
        }

        int getSize() {
            return array->getSize();
        }

        T pop() {
            return array->removeLast();
        }

        T peek() {
            return array->getLast();
        }

        void push(T e) {
            array->addLast(e);
        }

        bool isEmpty() {
            return array->isEmpty();
        }

        /**
        * 打印数组的所有元素
        */
        void print() {
            std::cout << "ArrayStack: size = " << array->getSize() << ", capacity = " << array->getCapacity() << std::endl;
            std::cout << "bottom ";
            array->print();
            std::cout << " top" << std::endl;
        }

    private:
        Array<T> *array;
    };
};

